//面试题 17.04. 消失的数字
/*数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

注意：本题相对书上原题稍作改动*/
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = n * (n + 1) / 2;
        int count = 0;
        for (auto& num : nums) {
            count += num;
        }
        return sum - count;
    }
};

//移除元素
/*给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。*/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = 0;
        while (right < nums.size()) {
            if (nums[right] != val) {
                swap(nums[right], nums[left]);
                left++;
            }
            right++;
        }
        return left;
    }
};


//合并两个有序数组
/*给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。*/
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums(nums1.begin(), nums1.begin() + m);
        int n1 = 0, n2 = 0;
        int index = 0;
        while (n1 < m || n2 < n) {
            if (n1 < m && n2 < n) {
                if (nums[n1] >= nums2[n2]) {
                    nums1[index++] = nums2[n2++];
                } else
                    nums1[index++] = nums[n1++];
            } else if (n1 < m) {
                nums1[index++] = nums[n1++];
            } else {
                nums1[index++] = nums2[n2++];
            }
        }
    }
};

//